package org.jspar.route;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

import org.jspar.Constants;
import org.jspar.Options;
import org.jspar.model.Module;
import org.jspar.model.Net;
import org.jspar.model.NetList;
import org.jspar.model.Terminal;
import org.jspar.tile.MutableTileDelegate;
import org.jspar.tile.Rectangle;
import org.jspar.tile.SVGExporter;
import org.jspar.tile.Tile;
import org.jspar.util.Identity;
import org.jspar.util.ListUtil;

public class GlobalRouting implements Constants{

	public static final int HORZ = 0;
	public static final int VERT = 1;
	
	private Tile[] routingRoot = new Tile[2];
	private Options configuration;
	private ICongestionRule setCongestionValue;
	private Map<Module, Tile> htile = new HashMap<Module, Tile>();
	private Map<Module, Tile> vtile = new HashMap<Module, Tile>();

	public GlobalRouting(Options conf) {
		this.configuration = conf;
	}

	/** This function creates the data structures used for global routing on
	 * the given page <p>. This should be called only once, and prior to the
	 * call to "first_global_route".
	 */
	public void createRoutingSpace(List<Module> ml, Rectangle bounds, NetList nets) {
		MutableTileDelegate mutableDelegate = new MutableTileDelegate();
		routingRoot[HORZ] = new Tile(
				bounds.x - CHANNEL_LENGTH - TERM_MARGIN,
				bounds.y - CHANNEL_LENGTH - TERM_MARGIN,
				bounds.width + 2 * CHANNEL_LENGTH + 2 * TERM_MARGIN,
				bounds.height + 2 * CHANNEL_HEIGHT + 2 * TERM_MARGIN,
				mutableDelegate);

		routingRoot[VERT] = new Tile(
				bounds.y - CHANNEL_HEIGHT - TERM_MARGIN,
				bounds.x - CHANNEL_LENGTH - TERM_MARGIN,
				bounds.height + 2 * CHANNEL_HEIGHT + 2 * TERM_MARGIN,
				bounds.width + 2 * CHANNEL_LENGTH + 2 * TERM_MARGIN,
				mutableDelegate);

		insertAllModules(routingRoot[HORZ], routingRoot[VERT], ml);
		
		reform_tile_space(routingRoot[HORZ].allspace(), HORZ);
	    reform_tile_space(routingRoot[VERT].allspace(), VERT);

		resetNetStructures(nets);
		
		mutableDelegate.setDelegate(new ArcTileDelegate());
	}

	private void reform_tile_space(List<Tile> tiles, int page) {
		for (Tile tl : tiles) {
			if (tl.content() == null)
				tl.setContent(new Arc(tl, page));
		}
	}

	private void resetNetStructures(NetList netlist) {
		for (Net net : netlist.nets()) {
			if (net.terminals().length > 0) {
				net.setStatus(0);
			} else {
				netlist.removeNet(net);
			}
		}
	}

	private void insertAllModules(Tile hroot, Tile vroot, List<Module> ml) {
		for (Module m : ml) {
			Rectangle r = m.type().assignTileDimensions(m);

			Arc arc = new Arc(r.width(), r.height(), HORZ, m);
			Tile t = hroot.insertTile(r.x(), r.y(), r.width(), r.height(), arc);
			arc.setTile(t);
			htile.put(m, t);
			if (t == null) {
				throw new RuntimeException("ERROR: " + m.type() + " module "
						+ m.name() + " did not insert into horz tilespace");
			}

			arc = new Arc(r.width(), r.height(), VERT, m);
			t = vroot.insertTile(r.y(), r.x(), r.height(), r.width(), arc);
			arc.setTile(t);
			vtile.put(m, t);
			if (t == null) {
				throw new RuntimeException("ERROR: " + m.type() + " module "
						+ m.name() + " did not insert into vert tilespace");
			}
			// m.clearFlag(Module.PLACED); /* Reuse of flag, now used for
			// printing */
		}
		SVGExporter.export("route.svg", hroot);
	}
	
	/**
	 * This function performs the global routing for the circuit. This begins by
	 * evaluating where the available routing space is.
	 * 
	 * This fn must be called at least once
	 * 
	 * This function is meant to serve in two modes: Either for creating a
	 * completed route on a completed routing space
	 * (non-incremental-mode:<onceOnly> == FALSE), or for completing the
	 * first-pass global route for a route that will be incrementally added to.
	 * (<onceOnly> == TRUE)
	 */
	public List<Net> firstGlobalRoute(List<Module> ml,
			boolean onceOnly) {

		selectCongestionRule(configuration.congestionRule);
		List<Expansion> expns = mapTerminalsIntoActiveExpansions(ml);

		/* Collect the nets that are being dealt with: */
		List<Net> activeNets = new ArrayList<Net>();
		for (Expansion exp : expns) {
			if (! activeNets.contains(exp.net()))
				activeNets.add(exp.net());
		}

		if (firstCut(expns) < 0) {
			return null;
		}

		if (!onceOnly && !configuration.stopAtFirstCut) {
			resetAllTrailCosts(activeNets);

			Iterator<Net> nets = activeNets.iterator();
			while (nets.hasNext()) {
				Net n = nets.next();
				if (n.terminals().length == 0)
					nets.remove();
			}

			Collections.sort(activeNets, new Comparator<Net>() {
				@Override
				public int compare(Net n1, Net n2) {
					return n1.netCost() - n2.netCost();
				}
			});
			for (Net n : activeNets) {
				improveRoute(n);
				setArcCosts(activeNets);
			}
		}
		return activeNets;
	}

	private void setArcCosts(List<Net> activeNets) {
		throw new RuntimeException();
	}

	private void improveRoute(Net n) {
		throw new RuntimeException();
	}

	private void resetAllTrailCosts(List<Net> nets) {
		for (Tile tl : routingRoot[VERT].allspace()) {
			((Arc) tl.content()).fullRehash();
		}
		for (Tile tl : routingRoot[HORZ].allspace()) {
			((Arc) tl.content()).fullRehash();
		}
		for (Net nl : nets) {
			Expansion ex = nl.getDone().get(0);

			for (Expansion exl : ex.getSiblings()) {
				ex.rehash();
			}
			for (Trail trl : ex.getConnections()) {
				trl.computeCost();
			}
		}
	}

	private int firstCut(List<Expansion> expns) {
		List<Expansion> expCopy = new ArrayList<Expansion>(expns);
	    makeFirstMoves(expCopy, expns);	
	    return moveExpns(expCopy);
	}

	private void makeFirstMoves(List<Expansion> activeExpns,
			List<Expansion> allExpns) {
		for (Expansion ex : allExpns) {
			Trail t = makeStartupTrail(ex, ex.initialMove(this, 0), 0);
			if (t.tiles().isEmpty()) {
				throw new RuntimeException(
						"make_first_moves: trail has NULL component");
			}
			Arc a = (Arc) t.tiles().get(0).content();
			a.insertTrailA(t);
			if (!check_for_AND_terminate_expn(t, activeExpns)) {
				ex.insertTrailE(t);
			}
		}
	}

	private boolean check_for_AND_terminate_expn(Trail t,
			List<Expansion> expnsStillActive) {
		Expansion parentEx = t.expansion();
		Arc a = (Arc) t.tiles().get(0).content();
		Trail besTrail = a.getBestTrail(parentEx);
		if (besTrail != null) {
			terminate_expansion(parentEx, besTrail.expansion(), a, t,
					expnsStillActive);
			return true;
		}
		return false;
	}

	private void terminate_expansion(Expansion ex, Expansion jEx, Arc jArc,
			Trail besTrail, List<Expansion> ActiveExpns) {
		int startCost = besTrail.cost();
		Net n = ex.net();
		Expansion whoStopped = null;

		for (Expansion exl : ex.getSiblings()) {
			if (ActiveExpns.remove(exl)) {
				whoStopped = exl;
				break;
			}
		}

		if (whoStopped != null) {
			n.addDone(whoStopped);
			if (whoStopped != ex) {
				whoStopped.adjust_trailset(ex);
			}
			jEx.getSiblings().addAll(ex.getSiblings());
			Trail sibTrail = jArc.best_trailA(jEx);
			boolean doAdd = false;
			for (Tile tl : sibTrail.tiles()) {
				if (doAdd || tl == jArc.tile()) {
					doAdd = true;
					besTrail.add_to_trail(tl);
				}
			}
			besTrail.setJoinExpansion(jEx);
			ex.getConnections().add(besTrail);
			jEx.getConnections().addAll(ex.getConnections());

			// is last expansion of this net to be done ?
			if (n.isLastExpansionToBeDone()) {
				Expansion newJex;
				Tile firsTile;
				if (ActiveExpns.contains(jEx)) {
					List<Tile> completionList = new ArrayList<Tile>(sibTrail.tiles());
					firsTile = completionList.get(0);
					sibTrail = new Trail(firsTile, jEx, sibTrail.page(), VERT, this);
					((Arc) sibTrail.tiles().get(0).content())
							.insertTrailA(sibTrail);
					sibTrail.setJoinExpansion(jEx);
					newJex = jEx;
				} else {
					newJex = ListUtil.member(jEx, ActiveExpns,
							new OnSameNet()).get(0);

					Terminal t = newJex.terminal();
					int xPos = t.x() + t.module().x()
							+ t.terminalSpacer(Constants.X);
					int yPos = t.y() + t.module().y()
							+ t.terminalSpacer(Constants.Y);

					firsTile = locateFirstTile(t.side(), xPos, yPos);
					sibTrail = new Trail(firsTile, newJex, sibTrail.page(), VERT, this);
					sibTrail.setJoinExpansion(newJex);
					((Arc) sibTrail.tiles().get(0).content())
							.insertTrailA(sibTrail);
				}

				if (firsTile == besTrail.tiles().get(
						besTrail.tiles().size() - 1))
					sibTrail.setJoinExpansion(besTrail.expansion());
				jEx.getConnections().add(sibTrail);
				n.addDone(newJex);
				ActiveExpns.remove(newJex);
			}
			for (Expansion exl : jEx.getSiblings()) {
				exl.merge(jEx);
			}
		}
	}

	private Trail makeStartupTrail(Expansion ex, Tile starTile, int page) {
		Trail tr;
		if (ex.terminal().side() == Terminal.LEFT
				|| ex.terminal().side() == Terminal.RIGHT) {
			tr = new Trail(starTile, ex, page, VERT, this);
		} else {
			tr = new Trail(starTile, ex, page, HORZ, this);
		}
		tr.computeCost();
		return tr;
	}
	
	private int moveExpns(List<Expansion> expnsToMove) {
		List<Trail> trailsCompleted = new ArrayList<Trail>();
		while (expnsToMove != null) {
			/*
			 * have all expansions (there is one for every terminal) made the
			 * least-expensive (upward?) expansions: - Do not enter an area to
			 * which this terminal has already expanded.
			 */

			/* Move all active expansion groups one step... */
			Collections.sort(expnsToMove, new InTrailOrder());
			for (Expansion exl : expnsToMove) {
				if (make_next_best_move(exl, trailsCompleted) < 0) {
					throw new RuntimeException(
							"move_expns:  make_next_best_move returned error condition");
				}
			}

			/* check all expansion groups for terminations: */
			Collections.sort(trailsCompleted);
			Iterator<Trail> it = trailsCompleted.iterator(); // XXX should make copy
			while (it.hasNext()) {
				Trail t = it.next();
				List<Expansion> terminationCandidates = t.check_for_termination();
				Iterator<Expansion> it2 = terminationCandidates.iterator(); // XXX should make copy
				while (it2.hasNext()) {
					Expansion jEx = it2.next();
					if (jEx != null) {
						Trail temp = t.expansion()
								.examineBestTrailInExpansionGroup();
						if (temp == t) {
							t.expansion().remove_trailE(t);
							terminate_expansion(t.expansion(), jEx, (Arc) t
									.tiles().get(0).content(), t, expnsToMove);
						}
					}
				}
			}
		}
		return 0;
	}

	private int make_next_best_move(Expansion ex, List<Trail> trailsCompleted) {
		List<Trail> activeTrails = new ArrayList<Trail>();

		Trail t = ex.examineBestTrailInExpansionGroup();

		if (t == null && (ex.getConnections() == null
						|| ((ex.net().getExpansions().size() - ex.net().getDone().size()) < 2))) {
			t = ex.restart_expansion();
			if (t == null) {
				return -1;
			} else {
				return -1;
			}
		}

		else if (t != null) {
			ex = t.expansion();
			t = ex.extract_best_trail_in_expn_group();

			Tile starTile = t.tiles().get(0);
			Tile lasTile = t.tiles().size() > 1 ? t.tiles().get(1) : starTile;
			Arc a = (Arc) starTile.content();

			List<Expansion> possibleTerminations = t.check_for_termination();

			if (possibleTerminations.isEmpty()) {
				List<Tile> tileSet = collect_tiles(starTile, routingRoot[t
						.direction()] /* [t.page] */);
				ex.remove_tiles_on_circular_trail(t, tileSet);
				if (tileSet.size() > 0) {
					for (Tile tl : tileSet) {
						Trail tempTrail = t.copy();
						tempTrail.add_to_trail(tl);
						ex.insertTrailE(tempTrail);
						activeTrails.add(tempTrail);
						a = (Arc) tl.content();
					}

					for (Tile tl : t.tiles()) {
						((Arc) tl.content()).remove_trailA(t);
					}
					t.add_to_trail(tileSet.get(0));
					ex.insertTrailE(t);
					activeTrails.add(t);
					a = (Arc) tileSet.get(0).content();
				}

				else {
					if (trailsCompleted.size() > 1
							&& t.jEx() != null
							&& ex.getSiblings().size() >= 2
							&& (ex.net().expansions().size() - ex.net()
									.getDone().size()) >= 2) {
						t.expansion().insertTrailE(t);
					} else {
						t.delete_trail();
					}
				}
				return 0;
			} else {
				t.expansion().insertTrailE(t);
				for (Expansion exl : possibleTerminations) {
					Expansion nextEx = exl;
					Trail tempTrail = nextEx.examineBestTrailInExpansionGroup();
					if (tempTrail == null || t.cost() <= tempTrail.cost())
						trailsCompleted.add(t);
					else {
						List<Expansion> secondaryTerminations = tempTrail
								.check_for_termination();
						if (ListUtil.isMember(t.expansion(),
								secondaryTerminations,
								new Identity<Expansion>())) {
							if (t.cost() < tempTrail.cost())
								trailsCompleted.add(t);
							else
								trailsCompleted.add(tempTrail);
						}
					}
				}
				return 0;
			}
		}
		return 0;
	}

	private List<Tile> collect_tiles(Tile starTile, Tile root) {
		return root.areaEnumerate(new FreeToRouteIn(),
				starTile.y(), starTile.x(),
				starTile.height(), starTile.width());
	}

	public Tile locateFirstTile(int side, int xPos, int yPos) {
		Tile hTile = null;

		if (side == Terminal.LEFT || side == Terminal.RIGHT) {
			hTile = routingRoot[HORZ].locate(xPos, yPos);
			if (hTile == null || hTile.bottom() == yPos) {
				hTile = hTile.locate(xPos, yPos + 1);
			}
			if (hTile == null) {
				hTile = routingRoot[VERT].locate(yPos, xPos);
			}
		} else {
			hTile = routingRoot[VERT].locate(yPos, xPos);
		}
		return hTile;
	}

	private List<Expansion> mapTerminalsIntoActiveExpansions(List<Module> ml) {
		List<Expansion> activeExpns = new ArrayList<Expansion>();

		for (Module mod : ml) {
			for (Terminal ter : mod.terminals()) {
				if (ter.net() != null && ter.net().terminals().length > 1
						&& ListUtil.isMember(ter, ter.net().terminals(), new Identity<Terminal>())) {
					for (Terminal trll : ter.net().terminals()) {
						if (!ListUtil.isMember(trll, activeExpns, new CheckTerminal())) {
							List<Expansion> oldExpns = ListUtil.member(trll,
									ter.net().expansions(), new CheckTerminal());
							if (oldExpns.isEmpty() && trll.net() != null) {
								activeExpns.add(new Expansion(trll));
							} else {
								activeExpns.add(oldExpns.get(0));
							}
						}
					}
				}
			}
		}
		return activeExpns;
	}

	private void selectCongestionRule(int congestionRule) {
		switch (congestionRule) {
		case 2:
			setCongestionValue = new ComplexCongestionRule();
			break;

		default:
			setCongestionValue = new SimpleCongestionRule();
			break;
		}
	}

	public static int toggleDirection(int page) {
		return page == HORZ ? VERT : HORZ;
	}

	public Tile getRootTile(int dir) {
		return routingRoot[dir];
	}

}
